//19. 删除链表的倒数第 N 个结点
//思路：1.给链表头加一个节点，这个节点作为新的链表头
//2.求出原链表的长度length，length-n 位置正好就是要删除节点的前一个位置
//3.将prev->next = prev->next->next，这样就实现了本题


#include <stdlib.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
int getLength(struct ListNode* head) {
	int length = 0;
	while (head)
	{
		length++;
		head = head->next;
	}
	return length;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (NULL == newhead)
	{
		perror("malloc fail:");
		return NULL;
	}
	newhead->val = 0;
	newhead->next = head;//原链表新加一个头节点，目的在于避免空指针异常问题

	int length = getLength(head);//求原链表的长度
	struct ListNode* prev = newhead;
	for (int i = 0; i < length - n; i++)//要删除的节点前一个节点就是新链表的length-n位置
	{
		prev = prev->next;
	}

	struct ListNode* del = prev->next;
	prev->next = prev->next->next;
	free(del);//这里也可以不释放

	head = newhead->next;//更新原链表的头结点
	free(newhead);
	return head;
}